Multilink protocols are well known in the art and have been standardized for both point-to-point protocol (MLPPP, also referred to as MP) and Frame Relay protocol (MLFR, also referred to as MFR), among others. Multilink protocols combine multiple physical or logical links and use them together as if they were one high-performance link. MLPPP is described in RFC 1717, which has been updated by RFC 1990. MLFR has is described by specifications FRF.15 and FRF.16
MLPPP and the MLFR Protocols function by fragmenting datagrams or frames and sending the fragments over different physical or logical links. Datagrams or frames received from any of the network layer protocols are first encapsulated into a modified version of the regular PPP or FR frame. A decision is then made about how to transmit the datagram or frame over the multiple links. Each fragment is encapsulated and sent over one of the links.
On a receiving end, the fragments received from all of the links are reassembled into the original PPP or FR frame. That frame is then processed like any other PPP or FR frame, by inspecting the Protocol field and passing the frame to the appropriate network layer protocol.
The fragmenting of data in multilink protocols introduces a number of complexities that the protocols must be equipped to handle. For example, since fragments are being sent roughly concurrently, they must be identified by a sequence number to enable reassembly. Control information for identifying the first and last fragments must also be incorporated in the fragment headers. A special frame format is used for the fragments to carry this information.
FIG. 1 is a schematic diagram illustrating two devices, 12 and 14, provisioned to support multilink protocol communications. A plurality of physical or logical links 16 are allocated to a “link bundle” that provides a single high-performance connection between the devices 12, 14. The devices 12, 14 may be routers, switches, or user terminals. The number of physical or logical links 16 allocated to a connection is a matter of resource availability and design choice. As is understood by those skilled in the art, a certain amount of buffering is required when terminating multiple links to compensate for variations in timing among the links and to account for lost fragments. When dealing with large numbers of link bundles, the requirement for buffering becomes significant and careful management is required.
When multiple links carry fragments simultaneously, it is not uncommon for a fragment to be lost. As shown in FIG. 1, a frame divided in to 15 fragments 18 is missing fragment “10”, as indicated by reference number 20. Existing prior art solutions typically implement a simple missing fragment cleaned up scheme and may also use a basic idle link detection scheme that relies on higher level software to handle detection of idle links, as described below with reference to FIGS. 3 and 4.
FIG. 2 is a flow chart illustrating a simple missing fragment clean-up algorithm commonly used in the prior art. At each fragment cleanup timeout, a fragment clean-up algorithm finds a next link bundle to check (step 30). The algorithm then determines whether the sequence number of fragments received from every link is greater than a smallest missing fragment sequence number (step 32). In the examples shown in FIG. 1, the smallest missing fragment sequence number is “10”, as described above. If it is determined in step 32 that the fragment sequence number received from each link was larger than the smallest missing sequence number, a buffer cleanup process is run (step 34) and the fragments stored in the buffer belonging to the incomplete frame must be discarded. The algorithm then waits for the next timeout (step 36) before branching back to find the next link bundle to check (step 30).
While the algorithm shown in FIG. 2 is relatively efficient at detecting missing fragments, it does not address the problem of idle links, sometimes referred to as “dead” links.
FIG. 3 is a schematic diagram of the devices shown in FIG. 1 illustrating a problem that arises when one of the physical or logical links in a link bundle becomes idle. In this example, link 22 becomes idle. Consequently, when a frame divided into 30 fragments is transmitted from device 12 to device 14, fragments 5, 10, 15, 20, 25 and 30 are missing. As will be understood by those skilled in the art, this poses a problem for the algorithm shown in FIG. 2. In order to address the problem, some prior art buffer cleanup algorithms rely on higher level software processes to detect idle links. Examples include Loss of Signal (LOS); Alarm Indication Signal (AIS); and, Link Control Protocol (LCP) timeouts, etc. however those higher level software processes generally require long detection times. Furthermore, those higher level software processes have no standardized hooks for freeing up buffers being used to reassembled packets or frames.
FIG. 4 is a flow chart illustrating a missing fragment cleanup algorithm that implements a basic idle link detection scheme. Each time the algorithm executes, it finds a next link bundle to check (step 40). It then determines whether the fragment sequence number received from every link is greater than the smallest missing fragment sequence number (step 42). If not, it determines whether a higher level process has reported a link failure (step 46). If the determination in either of steps 42 or 46 is true, the algorithm runs buffer cleanup (step 44). If not, the algorithm waits for the next timeout (step 48). As explained above, relying on the higher level software process to report link failure wastes valuable time and can lead to serious buffer congestion, buffer overflow and frame or packet loss.
It is therefore highly desirable to provide a method of reducing buffer usage by detecting missing fragments and idle links for multilink protocols. It is also highly desirable to provide devices that implement the method.